package tree;

import java.util.Arrays;

/**
 * @Author wangtengyu
 * @Create 2018-09-13-11:06
 *
 * 题目：输入一个序列 判断是否是二叉搜索树的后序序列 二叉搜索树：中序遍历 由小到大
 *
 * 二叉搜索树 后序遍历满足的条件就是 左子树小于根节点，右子树大于根节点 不满足这个条件的话就不是二叉搜索树后序遍历 记录左右子树，再对左右子树进行判断。
 */
public class IsPostOrder {

  public boolean isPostOrder(int[] array) {
    if (array == null || array.length <= 0) {
      return false;
    }

    int root = array[array.length - 1];

    //左子树索引范围
    int i = 0;
    for (; i < array.length - 1; i++) {
      if (array[i] > root) {
        break;
      }
    }

    int j = i;
    for (; j < array.length - 1; j++) {
      if (array[j] < root) {
        return false;
      }
    }
    boolean left = true;
    //判断有无左子树
    if (i > 0) {
      left = isPostOrder(Arrays.copyOfRange(array, 0, i));
    }

    boolean right = true;
    //判断有无右子树
    if (i < array.length - 1) {
      right = isPostOrder(Arrays.copyOfRange(array, i, array.length - 1));
    }

    return left && right;
  }


  public static void main(String[] args) {
    int[] array = new int[]{1, 3, 2, 5, 7, 6, 4};
    IsPostOrder isPostOrder = new IsPostOrder();
//        System.out.println(isPostOrder.isPostOrder(array));
    //只有后续遍历，可以画出多个树，所以不要靠想象些例子。程序是没问题的
    System.out.println(isPostOrder.isPostOrder(new int[]{7, 4, 6, 5}));
    System.out.println(isPostOrder.isPostOrder(new int[]{6, 7, 8, 5}));
  }
}
